package leetcode.editor.cn;

class CheckIfAWordOccursAsAPrefixOfAnyWordInASentence {
    public static void main(String[] args) {
        Solution solution = new CheckIfAWordOccursAsAPrefixOfAnyWordInASentence().new Solution();
        solution.isPrefixOfWord("i love eating burger", "burg");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // kmp不满足，求得需要是前缀
        /*public int isPrefixOfWord(String sentence, String searchWord) {
            String[] split = sentence.split(" ");
            int[] next = getNext(searchWord);
            int n = split.length;
            for (int m = 0; m < n; m++) {
                String s = split[m];
                int j = -1;
                for (int i = 0; i < s.length(); i++) {
                    while (j >= 0 && searchWord.charAt(j + 1) != s.charAt(i)) {
                        j = next[j];
                    }

                    if (searchWord.charAt(j + 1) == s.charAt(i)) {
                        j++;
                    }

                    if (j == next.length - 1) {
                        return m;
                    }
                }
            }

            return -1;
        }

        public int[] getNext(String s) {
            int n = s.length();
            char[] arr = s.toCharArray();
            int[] next = new int[n];
            int j = -1;
            next[0] = j;

            for (int i = 1; i < n; i++) {
                while (j >= 0 && arr[i] != arr[j + 1]) {
                    j = next[j];
                }

                if (arr[i] == arr[j + 1]) {
                    j++;
                }

                next[i] = j;
            }

            return next;
        }*/

        // 暴力
        public int isPrefixOfWord(String sentence, String searchWord) {
            String[] arr = sentence.split(" ");
            for (int i = 0; i < arr.length; i++) {
                if (arr[i].length() >= searchWord.length()) {
                    if (arr[i].substring(0, searchWord.length()).contains(searchWord)) {
                        return i;
                    }
                }
            }
            return -1;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
